package com.lw.leetcode.bingChaJi.b;

import java.util.*;

/**
 * Created with IntelliJ IDEA.
 * bingchaji
 * 947. 移除最多的同行或同列石头
 *
 * @author liw
 * @version 1.0
 * @date 2022/6/4 9:59
 */
public class RemoveStones {

    public static void main(String[] args) {
        RemoveStones test = new RemoveStones();

        // 5
//        int[][] arr = {{0, 0}, {0, 1}, {1, 0}, {1, 2}, {2, 1}, {2, 2}};

        // 3
//        int[][] arr = {{0, 0}, {0, 2}, {1, 1}, {2, 0}, {2, 2}};

        // 0
        int[][] arr = {{0, 0}};

        int i = test.removeStones(arr);
        System.out.println(i);
    }


    private Map<Integer, Integer> map = new HashMap<>();

    public int removeStones(int[][] stones) {
        int[] as = new int[10000];
        int[] bs = new int[10000];
        Arrays.fill(as, -1);
        Arrays.fill(bs, -1);
        for (int[] stone : stones) {
            int x = stone[0];
            int y = stone[1];
            int v = (x << 16) + y;
            int fx = v;
            int fy = v;
            if (as[x] == -1) {
                as[x] = v;
            } else {
                fx = find(as[x]);
                map.put(v, fx);
            }
            if (bs[y] == -1) {
                bs[y] = v;
            } else {
                fy = find(bs[y]);
                map.put(v, fy);
            }
            if (fx == v && fy == v) {
                map.put(v, v);
            } else if (fx == v) {
                map.put(v, fy);
            } else if (fy == v) {
                map.put(v, fx);
            } else {
                map.put(fy, fx);
            }
        }
        Set<Integer> set = new HashSet<>();
        for (int[] stone : stones) {
            int v = (stone[0] << 16) + stone[1];
            set.add(find(v));
        }
        return stones.length - set.size();
    }


    private int find(int key) {
        Integer v = map.get(key);
        if (v == null || v == key) {
            map.put(key, v);
            return key;
        }
        v = find(v);
        map.put(key, v);
        return v;
    }


}
